/* Parser.cs -- 
   Copyright (C) 2007, 2008  Casey Marshall.
   Copyright (C) 2008 Pacific Biosciences, Inc.

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */


using System;
using System.Collections.Generic;
using System.IO;

namespace SexpSharp
{
    public enum Format
    {
		Verbatim,
		Advanced,
		Transport
    }

    /// <summary>
    /// S-expression parser class.
    /// </summary>
    public class Parser
    {
		// Parsing state.
		enum State { Initial, ReadLength, ReadVerbatim, ReadToken,
					 ReadHex, ReadQuotedString, ReadBase64, EndOfInput };

		private static string B64CHARS
		= "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

		private MultiCallback callbacks;
		private Stream input;
		private State state;

		// State variables...
		private int listDepth;
		private int atomLength;
		private int atomRead;
		private bool atomIsMultipart;
		private MemoryStream atomBuffer;
		private int unreadChar;
		private int hexPart;
		private byte[] b64Part;
		private int b64Index;
		private int b64State;

		/// <summary>
		/// Creates a new s-expression parser.
		///
		/// <para>Since this parser cosumes most input one byte at a time,
		/// it is advisable to make the input stream buffered.</para>
		/// </summary>
		///
		/// <param name="input">The input stream. Must be
		/// readable.</param>
		public Parser(Stream input)
		{
			if (!input.CanRead)
				throw new IOException("needs a readable stream");
			callbacks = new MultiCallback();
            if (input is BufferedStream)
                this.input = input;
            else
                this.input = new BufferedStream(input);
			state = State.Initial;
			listDepth = 0;
			atomBuffer = new MemoryStream();
			unreadChar = -1;
			hexPart = -1;
			b64Part = new byte[3];
			b64Index = 0;
			b64State = 1;
		}

		public void AddCallback(ParseCallback cb)
		{
			callbacks.AddCallback(cb);
		}

		public void RemoveCallback(ParseCallback cb)
		{
			callbacks.RemoveCallback(cb);
		}

		/// <summary>
		/// Consume "some" of the input stream; for most tokens, only a
		/// single character is read from the underlying stream. For
		/// others (escape sequences in quoted strings, verbatim atoms)
		/// more than one character may be consumed.
		/// </summary>
		public void Consume()
		{
			switch (state)
			{
			case State.Initial:
			{
				int c = input.ReadByte();
				if (c == '(')
				{
					listDepth++;
					callbacks.OnListBegin();
				}
				else if (c == ')')
				{
					listDepth--;
					if (listDepth < 0)
						throw new ParseException("extra `)' in input");
					callbacks.OnListEnd();
				}
				else if (c == '#')
				{
					atomIsMultipart = false;
					state = State.ReadHex;
					atomBuffer.SetLength(0);
				}
				else if (c == '|')
				{
					atomIsMultipart = false;
					state = State.ReadBase64;
					atomBuffer.SetLength(0);
				}
				else if (c == '"')
				{
					atomIsMultipart = false;
					state = State.ReadQuotedString;
					atomBuffer.SetLength(0);
				}
				else if (Char.IsDigit((char) c))
				{
					atomLength = (c - '0');
					state = State.ReadLength;
					atomBuffer.SetLength(0);
				}
				else if (Char.IsWhiteSpace((char) c))
				{
					// ignored
				}
				else if (c == -1)
				{
					if (listDepth != 0)
						throw new ParseException("list did not end at end of input");
					state = State.EndOfInput;
					callbacks.OnEndOfInput();
				}
				else if (IsTokenStart(c))
				{
					atomIsMultipart = false;
					state = State.ReadToken;
					atomBuffer.SetLength(0);
					atomBuffer.WriteByte((byte) c);
				}
				else
					throw new ParseException("invalid character `" + ((char) c)
											 + "' in input");
			}
			break;

			case State.ReadLength:
			{
				int c = input.ReadByte();
				if (c == ':')
				{
					callbacks.OnAtomBegin(atomLength);
					atomRead = 0;
					if (atomLength == 0)
					{
						callbacks.OnAtomEnd();
						state = State.Initial;
					}
					else
						state = State.ReadVerbatim;
				}
				else if (c == '#')
				{
					atomIsMultipart = true;
					callbacks.OnAtomBegin(atomLength);
					state = State.ReadHex;
					atomBuffer.SetLength(0);
					if (atomLength > 0)
						atomBuffer.Capacity = atomLength;
				}
				else if (c == '|')
				{
					atomIsMultipart = true;
					callbacks.OnAtomBegin(atomLength);
					state = State.ReadBase64;
					atomBuffer.SetLength(0);
					if (atomLength > 0)
						atomBuffer.Capacity = atomLength;
				}
				else if (c == '"')
				{
					atomIsMultipart = true;
					callbacks.OnAtomBegin(atomLength);
					state = State.ReadQuotedString;
					atomBuffer.SetLength(0);
					if (atomLength > 0)
						atomBuffer.Capacity = atomLength;
				}
				else if (Char.IsDigit((char) c))
				{
					int x = atomLength;
					x = (x * 10) + (c - '0');
					if (x < atomLength)
						throw new ParseException("integer overflow with atom length");
					atomLength = x;
				}
				else
				{
					throw new ParseException("invalid character `" + ((char) c)
											 + "' following atom length");
				}
			}
			break;

			case State.ReadVerbatim:
			{
				byte[] buffer = new byte[Math.Min(atomLength - atomRead, 1024)];
				int x = input.Read(buffer, 0, buffer.Length);
				if (x == 0)
					throw new ParseException("end of input reading atom");
				callbacks.OnAtomData(buffer, 0, x);
				atomRead += x;
				if (atomRead == atomLength)
				{
					callbacks.OnAtomEnd();
					state = State.Initial;
				}
			}
			break;

			case State.ReadToken:
			{
				int c = input.ReadByte();
				if (IsTokenPart(c))
					atomBuffer.WriteByte((byte) c);
				else if (c == -1)
					throw new ParseException("unexpected end of input");
				else if (Char.IsWhiteSpace((char) c))
				{
					callbacks.OnAtom(atomBuffer.ToArray(), 0,
									 (int) atomBuffer.Length);
					state = State.Initial;
				}
				else if (c == ')')
				{
					callbacks.OnAtom(atomBuffer.ToArray(), 0,
									 (int) atomBuffer.Length);
					listDepth--;
					if (listDepth < 0)
						throw new ParseException("extra `)' in input");
					callbacks.OnListEnd();
					state = State.Initial;
				}
				else if (c == '(')
				{
					callbacks.OnAtom(atomBuffer.ToArray(), 0,
									 (int) atomBuffer.Length);
					listDepth++;
					callbacks.OnListBegin();
					state = State.Initial;
				}
				else
					throw new ParseException("invalid token character `"
											 + ((char) c) + "'");
			}
			break;

			case State.ReadHex:
			{
				int c = input.ReadByte();
				if (IsHexDigit(c))
				{
					if (hexPart == -1)
						hexPart = FromHexDigit(c);
					else
					{
						hexPart = (hexPart << 4) | FromHexDigit(c);
						atomBuffer.WriteByte((byte) hexPart);
						hexPart = -1;
					}
				}
				else if (c == '#')
				{
					if (hexPart != -1)
						throw new ParseException("hexadecimal encoding cannot have an odd "
												 + "number of characters");
					if (atomIsMultipart)
					{
						if (atomBuffer.Length != atomLength)
							throw new ParseException("hex value not declared size");
						callbacks.OnAtomData(atomBuffer.ToArray(), 0, (int) atomBuffer.Length);
						callbacks.OnAtomEnd();
					}
					else
						callbacks.OnAtom(atomBuffer.ToArray(), 0, (int) atomBuffer.Length);
					state = State.Initial;
				}
				else if (Char.IsWhiteSpace((char) c))
					;
				else if (c == -1)
					throw new ParseException("unexpected end of input");
				else
					throw new ParseException("invalid character in hex value");
			}
			break;

			case State.ReadQuotedString:
			{
				int c;
				if (unreadChar != -1)
				{
					c = unreadChar;
					unreadChar = -1;
				}
				else
					c = input.ReadByte();

				if (IsQuotableChar(c))
					atomBuffer.WriteByte((byte) c);
				else if (c == '\\')
				{
					int cc = input.ReadByte();
					if (cc == 'b')
						atomBuffer.WriteByte((byte) '\b');
					else if (cc == 't')
						atomBuffer.WriteByte((byte) '\t');
					else if (cc == 'v')
						atomBuffer.WriteByte((byte) '\v');
					else if (cc == 'n')
						atomBuffer.WriteByte((byte) '\n');
					else if (cc == 'f')
						atomBuffer.WriteByte((byte) '\f');
					else if (cc == 'r')
						atomBuffer.WriteByte((byte) '\r');
					else if (cc == '"')
						atomBuffer.WriteByte((byte) '"');
					else if (cc == '\'')
						atomBuffer.WriteByte((byte) '\'');
					else if (cc == '\\')
						atomBuffer.WriteByte((byte) '\\');
					else if (cc >= '0' && cc <= '7')
					{
						int cc2 = input.ReadByte();
						int cc3 = input.ReadByte();
						if (cc2 == -1 || cc3 == -1)
							throw new ParseException("end of input reading octal sequence");
						if (cc2 < '0' || cc2 > '7' || cc3 < '0' || cc3 > '7')
							throw new ParseException("invalid octal character");
						int o = ((cc - '0') << 6) | ((cc - '0') << 3) | (cc - '0');
						atomBuffer.WriteByte((byte) o);
					}
					else if (cc == 'x')
					{
						int x1 = input.ReadByte();
						int x2 = input.ReadByte();
						if (x1 == -1 || x2 == -1)
							throw new ParseException("end of input reading hex sequence");
						if (!IsHexDigit(x1) || !IsHexDigit(x2))
							throw new ParseException("invalid hexadecimal character");
						int x = (FromHexDigit(x1) << 4) | FromHexDigit(x2);
						atomBuffer.WriteByte((byte) x);
					}
					else if (cc == '\n')
					{
						int ccc = input.ReadByte();
						if (ccc != '\r')
							unreadChar = ccc;
						// chars are ignored
					}
					else if (cc == '\r')
					{
						int ccc = input.ReadByte();
						if (ccc != '\n')
							unreadChar = ccc;
						// chars are ignored
					}
				}
				else if (c == '"')
				{
					if (atomIsMultipart)
					{
						if (atomBuffer.Length != atomLength)
							throw new ParseException("quoted string is not declared length "
													 + " (expecting: " + atomLength + ", "
													 + " actual: " + atomBuffer.Length + ")");
						callbacks.OnAtomData(atomBuffer.ToArray(), 0,
											 (int) atomBuffer.Length);
						callbacks.OnAtomEnd();
						atomBuffer.SetLength(0);
					}
					else
					{
						callbacks.OnAtom(atomBuffer.ToArray(), 0,
										 (int) atomBuffer.Length);
						atomBuffer.SetLength(0);
					}
					state = State.Initial;
				}
				else if (c == -1)
					throw new ParseException("unexpected end of input");
				else
					throw new ParseException("illegal character `" + ((char) c)
											 + "' in quoted string");
			}
			break;

			case State.ReadBase64:
			{
				int c = input.ReadByte();
				if (c == -1)
					throw new ParseException("unexpected end of input in base 64 sequence");
				if (c == '|')
				{
					if (b64State != 1)
						throw new ParseException("base 64 sequence ends prematurely");
					if (atomIsMultipart)
					{
						if (atomBuffer.Length != atomLength)
							throw new ParseException("base 64 sequence is not the declared length");
						callbacks.OnAtomData(atomBuffer.ToArray(), 0, (int) atomBuffer.Length);
						callbacks.OnAtomEnd();
					}
					else
					{
						callbacks.OnAtom(atomBuffer.ToArray(), 0, (int) atomBuffer.Length);
					}
					state = State.Initial;
					break;
				}
				if (Char.IsWhiteSpace((char) c))
					break; // Ignore white space.
				int x;
				switch (b64State)
				{
				case 1:
					x = B64CHARS.IndexOf((char) c);
					if (x == -1)
						throw new ParseException("invalid base 64 character: " + ((char) c));
					b64Part[0] = (byte) (x << 2);
					b64State = 2;
					break;

				case 2:
					x = B64CHARS.IndexOf((char) c);
					if (x == -1)
						throw new ParseException("invalid base 64 character: " + ((char) c));
					b64Part[0] |= (byte) ((x >> 4) & 0x3);
					b64Part[1] = (byte) ((x & 0xf) << 4);
					b64Index++;
					b64State = 3;
					break;

				case 3:
					if (c == '=')
					{
						b64State = 4;
						break;
					}
					x = B64CHARS.IndexOf((char) c);
					if (x == -1)
						throw new ParseException("invalid base 64 character: " + ((char) c));
					b64Part[1] |= (byte) ((x >> 2) & 0xf);
					b64Part[2] = (byte) ((x & 3) << 6);
					b64Index++;
					b64State = 4;
					break;

				case 4:
					if (c == '=')
					{
						b64State = 1;
						break;
					}
					x = B64CHARS.IndexOf((char) c);
					if (x == -1)
						throw new ParseException("invalid base 64 character: " + ((char) c));
					if (b64Index != 2)
						throw new ParseException("invalid base 64 padding character");
					b64Part[2] |= (byte) (x & 0x3f);
					b64Index++;
					b64State = 1;
					break;
				}
				if (b64State == 1)
				{
					atomBuffer.Write(b64Part, 0, b64Index);
					b64Part[0] = b64Part[1] = b64Part[2] = 0;
					b64Index = 0;
				}
			}
			break;
			}
		}

		public void Parse()
		{
			while (state != State.EndOfInput)
				Consume();
		}

		public static void Parse(Stream input, ParseCallback cb)
		{
			Parser p = new Parser(input);
			if (cb != null)
				p.AddCallback(cb);
			p.Parse();
		}

		public static Expression Parse(Stream input)
		{
			BuilderCallback cb = new BuilderCallback();
			Parser p = new Parser(input);
			p.AddCallback(cb);
			while (!cb.Finished && !cb.EndOfInput)
				p.Consume();
			return cb.Expression;
		}

		public static IList<Expression> ParseAll(Stream input)
		{
			List<Expression> exprs = new List<Expression>();
			Expression e;
			while ((e = Parse(input)) != null)
				exprs.Add(e);
			return exprs;
		}

		public static bool IsTokenPart(int ch)
		{
			return (Char.IsDigit((char) ch) || IsTokenStart(ch));
		}

		public static bool IsTokenStart(int ch)
		{
			return (Char.IsLetter((char) ch) || ch == '-'
					|| ch == '.' || ch == '/' || ch == '_'
					|| ch == ':' || ch == '*' || ch == '+'
					|| ch == '=');
		}

		public static bool IsQuotableChar(int ch)
		{
			return (IsTokenPart(ch) || ch == ' '
					|| ch == '\t' || ch == '('
					|| ch == ')' || ch == '['
					|| ch == ']' || ch == '{'
					|| ch == '}' || ch == '|'
					|| ch == '#' || ch == '&'
                    || ch == ',' || ch == '`');
		}

		public static bool IsHexDigit(int ch)
		{
			return (Char.IsDigit((char) ch) || (ch >= 'a' && ch <= 'f')
					|| (ch >= 'A' && ch <= 'F'));
		}

		public static int FromHexDigit(int ch)
		{
			if (ch >= '0' && ch <= '9')
				return (ch - '0');
			if (ch >= 'a' && ch <= 'f')
				return (ch - 'a') + 10;
			if (ch >= 'A' && ch <= 'F')
				return (ch - 'A') + 10;
			return -1;
		}

		internal class BuilderCallback : ParseCallback
		{
			internal BuilderCallback()
			{
				Reset();
			}

			internal void Reset()
			{
				depth = 0;
				listStack = new Stack<List>();
				atomBuffer = new MemoryStream();
				finished = false;
				eof = false;
			}

			public Expression Expression
			{
				get {
					if (finished)
						return expr;
					return null;
				}
			}

			public void OnListBegin()
			{
				List list = new List();
				if (current != null)
					current.Add(list);
				else
					expr = list;
				listStack.Push(current);
				current = list;
			}

			public void OnListEnd()
			{
				if (listStack.Count > 0)
					current = listStack.Pop();
				else if (current != null)
					current = null;
				else
					throw new ParseException("extra list end");

				if (current == null)
					finished = true;
			}

			public void OnAtomBegin(int atomLength)
			{
				atomBuffer.SetLength(0);
				if (atomLength > 0)
					atomBuffer.Capacity = atomLength;
			}

			public void OnAtomData(byte[] input, int offset, int length)
			{
				atomBuffer.Write(input, offset, length);
			}

			public void OnAtomEnd()
			{
				Atom atom = new Atom(atomBuffer.ToArray());
				if (current == null)
				{
					finished = true;
					expr = atom;
				}
				else
					current.Add(atom);
			}

			public void OnAtom(byte[] atomBytes, int offset, int length)
			{
				Atom atom = new Atom(atomBytes, offset, length);
				if (current == null)
				{
					finished = true;
					expr = atom;
				}
				else
					current.Add(atom);
			}

			public void OnEndOfInput()
			{
				eof = true;
			}

			internal bool Finished
			{
				get
				{
					return finished;
				}
			}

			internal bool EndOfInput
			{
				get {
					return eof;
				}
			}

			private int depth;
			private Expression expr;
			private Stack<List> listStack;
			private List current;
			private MemoryStream atomBuffer;
			private bool finished;
			private bool eof;
		}
    }
}
